package searchandsort;

public class SearchInRotatedSortedArrayii81 {
    public boolean search(int[] nums, int target) {
        return search(0, nums.length - 1, nums, target);
    }

    private boolean search(int begin, int end, int[] nums, int target) {
        if (begin > end) {
            return false;
        }
        int mid = (begin + end) / 2;
        if (nums[mid] == target) {
            return true;
        }

        if (nums[mid] == nums[begin] && nums[mid] == nums[end]) {
            return search(begin + 1, end - 1, nums, target);
        }

        if (nums[begin] <= nums[mid] && nums[mid]>nums[end]) {
            if (target >= nums[begin] && target < nums[mid]) {
                return search(0, mid - 1, nums, target);
            } else {
                return search(mid + 1, end, nums, target);
            }
        }
        if (nums[mid] <= nums[end]) {
            if (target > nums[mid] && target <= nums[end]) {
                return search(mid + 1, end, nums, target);
            } else {
                return search(0, mid - 1, nums, target);
            }
        }
        return false
                ;

    }
}
